#pragma once
#include <string.h>
#include <stdlib.h>
#include <time.h>

//----------------------------------------------------------------------------
// NOTE:
//
// The following code was developed by Arthur Liberman and Alexandra Yasny
// mostly for this project (Pascal-like Compiler), but also for learning 
// of how a well implemented hash table should be designed.
//----------------------------------------------------------------------------

// An abstract class which defines an interface for our HashTable classes
// to use to get the hash code values.
// HashClass derivatives will implement the specific hashing algorithms
class HashClass
{
public:
	virtual unsigned GetHash(char *i_Key) const = 0;
};

// Information about the following algorithms can be found here: 
// http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx

// JSW algorithm for creating well destributed hash codes.
class JswHashClass : public HashClass
{
public:
	JswHashClass()
	{
		srand((unsigned int)time(NULL));
		for (int i = 0; i < 256; i++)
		{
			this->m_Table[i] = rand();
		}
	}

	unsigned GetHash(char *i_Key) const
	{
		unsigned h = 16777551;
 
		for (; *i_Key; i_Key++)
		{
			h = (h << 1 | h >> 31) ^ this->m_Table[*i_Key];
		}
 
		return h;
	}

private:

	int m_Table[256];
};

// ELF is another well known algorithm for its very well destributed hash codes.
class ElfHashClass : public HashClass
{
public:
	unsigned GetHash(char *i_Key) const
	{
		unsigned h = 0, g;
 
		for (; *i_Key; i_Key++)
		{
			h = (h << 4) + *i_Key;
			g = h & 0xf0000000L; 
			if (g != 0)
			{
				h ^= g >> 24;
			}

			h &= ~g;
		}

		return h;	
	}
};

//////////////////////////////////////////////
///   struct HashTableEntry: declaration   ///
//////////////////////////////////////////////

// A structure, containing the actual value which is 
// to be added to a hash table and its key.
template <class Value>
struct HashTableEntry
{
public:
	HashTableEntry(char *i_Key, Value *i_Value, bool i_FreeMemory = true);
	~HashTableEntry();

	char *GetKey() const;
	Value *GetValue() const;
	
	bool operator==(const HashTableEntry<Value> &i_Entry);
	bool operator!=(const HashTableEntry<Value> &i_Entry);

private:
	char *m_Key;
	Value *m_Value;
	bool m_FreeMemory;
};

/////////////////////////////////////////////////
///   struct HashTableEntry: implementation   ///
/////////////////////////////////////////////////

// The implementation is straight forward, simply store a point 
// to the value and a copy of the key.
template <class Value>
HashTableEntry<Value>::HashTableEntry(char *i_Key, Value *i_Value, bool i_FreeMemory)
{
	this->m_Key = ::strdup(i_Key);
	this->m_Value = i_Value;
	this->m_FreeMemory = i_FreeMemory;
}

// Free memory.
template <class Value>
HashTableEntry<Value>::~HashTableEntry()
{
	::free(this->m_Key);
	if (this->m_FreeMemory)
	{
		delete [] this->m_Value;
	}
}

template <class Value>
char *HashTableEntry<Value>::GetKey() const
{
	return this->m_Key;
}

template <class Value>
Value *HashTableEntry<Value>::GetValue() const
{
	return this->m_Value;
}

template <class Value>
bool HashTableEntry<Value>::operator==(const HashTableEntry<Value> &i_Entry)
{
	bool result = this->m_Key == i_Entry.m_Key;
	
	if (!result)
	{
		result = ::strcmp(this->m_Key, i_Entry.m_Key) == 0;
	}

	return result;
}

template <class Value>
bool HashTableEntry<Value>::operator!=(const HashTableEntry<Value> &i_Entry)
{
	return !(*this == i_Entry);
}

////////////////////////////////////////////
///   class HashTableBase: declaration   ///
////////////////////////////////////////////

// An abstract class which implements the basics for a hash table
// and declares all the required functionality which must be 
// implemented by the derivatives.
template <class Value, class BucketType>
class HashTableBase
{
public:
	HashTableBase(int i_Buckets = 1000);
	HashTableBase(HashClass &i_HashClass, int i_Buckets = 1000);
	virtual ~HashTableBase(void);

	virtual bool Add(char *i_Key, Value *i_Value) = 0;
	virtual bool Remove(char *i_Key) = 0;
	virtual HashTableEntry<Value> *GetEntry(char *i_Key, int i_Index) const = 0;
	Value *GetValue(char *i_Key) const;

	int GetTableSize() const;
	int GetItemCount() const;
	void EnableAutoFreeMemory(bool i_Value);
	
	Value *operator[](char *i_Key);

protected:
	int GetIndex(char *i_Key) const;
	bool IsAutoFreeMemory() const;

	HashClass &m_HashClass;
	int m_ItemCount;
	const int k_TableSize;
	BucketType **m_Buckets;

private:
	void initializeHashTable();

	bool m_AutoFreeMemory;
	static ElfHashClass s_ElfHashClass;
};

///////////////////////////////////////////////
///   class HashTableBase: implementation   ///
///////////////////////////////////////////////

// Constructors and a destructor to initialize and
// deinitialize the class.
template <class Value, class BucketType>
HashTableBase<Value, BucketType>::HashTableBase(HashClass &i_HashClass, int i_Buckets)
	: k_TableSize(i_Buckets), m_HashClass(i_HashClass)
{
	this->initializeHashTable();
}

template <class Value, class BucketType>
HashTableBase<Value, BucketType>::HashTableBase(int i_Buckets)
	: k_TableSize(i_Buckets), m_HashClass(s_ElfHashClass)
{
	this->initializeHashTable();
}

template <class Value, class BucketType>
HashTableBase<Value, BucketType>::~HashTableBase(void)
{
	for (int i = 0; i < this->k_TableSize; i++)
	{
		delete this->m_Buckets[i];
	}

	delete [] this->m_Buckets;
}

// Retrieves the value from the HashTable. If an entry is found, it's
// value is returned, NULL otherwise.
template <class Value, class BucketType>
Value *HashTableBase<Value, BucketType>::GetValue(char * i_Key) const
{
	HashTableEntry<Value> *entry = this->GetEntry(i_Key, this->GetIndex(i_Key));

	return (entry) ? entry->GetValue() : NULL;
}

// Overloads the [] operator for simple access to HashTable values.
template <class Value, class BucketType>
Value *HashTableBase<Value, BucketType>::operator[] (char *i_Key)
{
	return this->GetValue(i_Key);
}

template <class Value, class BucketType>
int HashTableBase<Value, BucketType>::GetItemCount() const
{
	return this->m_ItemCount;
}

template <class Value, class BucketType>
int HashTableBase<Value, BucketType>::GetTableSize() const
{
	return this->k_TableSize;
}

// A flag which allows the user to choose whether he prefers that the 
// HashTable will automatically free memory when an item is removed or
// the table has been deinitialized.
template <class Value, class BucketType>
void HashTableBase<Value, BucketType>::EnableAutoFreeMemory(bool i_Value)
{
	this->m_AutoFreeMemory = i_Value;
}

template <class Value, class BucketType>
bool HashTableBase<Value, BucketType>::IsAutoFreeMemory() const
{
	return this->m_AutoFreeMemory;
}

// Returns the index in the local bucket array at which the value 
// is/should be located.
template <class Value, class BucketType>
int HashTableBase<Value, BucketType>::GetIndex(char *i_Key) const
{
	return this->m_HashClass.GetHash(i_Key) % this->k_TableSize;
}

template <class Value, class BucketType>
void HashTableBase<Value, BucketType>::initializeHashTable()
{
	this->m_ItemCount = 0;
	this->m_AutoFreeMemory = false;
	this->m_Buckets = new BucketType *[this->k_TableSize];
	memset(this->m_Buckets, 0, sizeof(BucketType *) * this->k_TableSize);
}

// By default the HashTable will implement the ELF hashing algorithm.
template <class Value, class BucketType>
ElfHashClass HashTableBase<Value, BucketType>::s_ElfHashClass;